`:top

The `!digraph realization problem`! is a `F33f`_`[decision problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decision_problem]`_`f in `F33f`_`[graph theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_theory]`_`f. Given pairs of nonnegative `F33f`_`[integers`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Integer]`_`f ( ( a 1 , b 1 ) , … … , ( a n , b n ) ) {\\displaystyle ((a_{1},b_{1}),\\ldots ,(a_{n},b_{n}))} , the problem asks whether there is a labeled `F33f`_`[simple directed graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f such that each `F33f`_`[vertex`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Vertex_(graph_theory)]`_`f v i {\\displaystyle v_{i}} has `F33f`_`[indegree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f a i {\\displaystyle a_{i}} and `F33f`_`[outdegree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f b i {\\displaystyle b_{i}} .

>>Contents

• `F0af`_`[Solutions`#solutions]`_`f

• `F0af`_`[Other Notations`#other-notations]`_`f

• `F0af`_`[Related problems`#related-problems]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Solutions

The problem belongs to the complexity class `F33f`_`[P`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=P_(complexity)]`_`f. Two algorithms are known to prove that. The first approach is given by the `F33f`_`[Kleitman–Wang algorithms`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Kleitman–Wang_algorithms]`_`f constructing a special solution with the use of a `F33f`_`[recursive algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Recursion_(computer_science)]`_`f. The second one is a characterization by the `F33f`_`[Fulkerson–Chen–Anstee theorem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Fulkerson–Chen–Anstee_theorem]`_`f, i.e. one has to validate the correctness of n {\\displaystyle n} inequalities.

>>Other Notations

The problem can also be stated in terms of zero-one `F33f`_`[matrices`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Matrix_(mathematics)]`_`f. The connection can be seen if one realizes that each `F33f`_`[directed graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f has an `F33f`_`[adjacency matrix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Adjacency_matrix]`_`f where the column sums and row sums correspond to ( a 1 , ⋯ ⋯ , a n ) {\\displaystyle (a_{1},\\cdots ,a_{n})} and ( b 1 , … … , b n ) {\\displaystyle (b_{1},\\ldots ,b_{n})} . Note that the diagonal of the matrix only contains zeros. The problem is then often denoted by `*0-1-matrices for given row and column sums`*. In the classical literature the problem was sometimes stated in the context of `F33f`_`[contingency tables`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Contingency_table]`_`f by `*contingency tables with given marginals`*.

>>Related problems

Similar problems describe the `F33f`_`[degree sequences`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Degree_(graph_theory)]`_`f of `F33f`_`[simple graphs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_theory]`_`f, `F33f`_`[simple directed graphs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f with `F33f`_`[loops`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f, and `F33f`_`[simple bipartite graphs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bipartite_graph]`_`f. The first problem is the so-called `F33f`_`[graph realization problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_realization_problem]`_`f. The second and third one are equivalent and are known as the `F33f`_`[bipartite realization problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bipartite_realization_problem]`_`f. `F33f`_`[Chen (1966)`#citerefchen1966]`_`f gives a characterization for `F33f`_`[directed multigraphs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multigraph]`_`f with a bounded number of parallel arcs and loops to a given `F33f`_`[degree sequence`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f. The additional constraint of the acyclicity of the directed graph is known as `*dag realization`*. `F33f`_`[Nichterlein & Hartung (2012)`#citerefnichterleinhartung2012]`_`f proved the `F33f`_`[NP-completeness`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-complete]`_`f of this problem. `F33f`_`[Berger & Müller-Hannemann (2011)`#citerefbergerm-ller-hannemann2011]`_`f showed that the class of opposed sequences is in `F33f`_`[P`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=P_(complexity)]`_`f. The problem `*uniform sampling a directed graph to a fixed degree sequence`* is to construct a solution for the digraph realization problem with the additional constraint that such each solution comes with the same probability. This problem was shown to be in `F33f`_`[FPTAS`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Polynomial-time_approximation_scheme]`_`f for regular sequences by `F33f`_`[Catherine Greenhill`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Catherine_Greenhill]`_`f (`F33f`_`[2011`#citerefgreenhill2011]`_`f) The general problem is still unsolved.

>>References

• `:citerefchen1966`aChen, Wai-Kai (1966), "On the realization of a (`*p`*,`*s`*)-digraph with prescribed degrees", `*Journal of the Franklin Institute`*, `!103`!: 406–422

• `:citerefnichterleinhartung2012`aNichterlein, André; Hartung, Sepp (2012), "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs", `*Journal of the Franklin Institute`*, `!7318`!: 283–292

• `:citerefbergerm-ller-hannemann2011`aBerger, Annabell; Müller-Hannemann, Matthias (2011), "Dag Realizations of Directed Degree Sequences", `*Proceedings of the 18th International Conference on Fundamentals of Computation Theory`*: 264–275

• `:citerefgreenhill2011`a`F33f`_`[Greenhill, Catherine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Catherine_Greenhill]`_`f (2011), "A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs", `*Electronic Journal of Combinatorics`*, `!18`!

`c`F0af`_`[↑ Back to top`#top]`_`f`a